/**
 * created by lpw
 */
public class TestClass {

    public static void main(String[] args) {
        int array[]={-4,2,10,9,8,7,6};
        quickSort(array,0,array.length-1);
        System.out.print(printArray(array));
        System.out.println();
        int K=3;
        System.out.println(String.format("第%d小的数为:%d",K,array[K-1]));

    }

    public static void quickSort(int[] array,int start,int end){
        if (start>=end){
            return;
        }
        int pivotPos=getPivotPos(array,start,end);
        quickSort(array,start,pivotPos);
        quickSort(array,pivotPos+1,end);
    }

    public static int getPivotPos(int[] array,int start,int end){
        int temp= array[start],t;
        int left=start;
        int right=end;
        while (left<right){
            //从右开始数，找到比选定的数大的那个数的下标
            while (temp<=array[right] && left<right){
                right--;
            }
            //从左开始数，找到比选定的数小的那个数的下标
            while (temp>=array[left] && left<right){
                left++;
            }
            //然后两个数互换位置
            if (left<right){
                t=array[left];
                array[left]=array[right];
                array[right]=t;
            }
        }
        //结束了循环，此时说明有left=right，
        array[start]=array[left];
        array[left]=temp;
        return left;
    }

    private static String printArray(int[] array) {
        StringBuffer sb=new StringBuffer("[");
        for (int i=0;i<array.length;i++) {
            sb.append(array[i]);
            if (i==array.length-1) break;
            sb.append(",");
        }
        sb.append("]");
        return sb.toString();
    }
}